package p03_SingleLinkedList.quiz.q01_剑指Offer22_链表中倒数第k个节点;

import org.junit.jupiter.api.Test;
import p03_SingleLinkedList.HeroNode;

//Definition for singly-linked list.
public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

class Solution {
    public static ListNode getKthFromEnd(ListNode head, int k) {
        int len = getLength(head);
        if (len == 0 || len < k || k < 1) {
            return null;
        }
        ListNode temp = head;
        int i = 0;
        while (len - i != k) {
            i++;
            temp = temp.next;
        }
        return temp;
    }

    public static int getLength(ListNode head) {
        if (head == null) {
            return 0;
        }
        int len = 0;
        ListNode temp = head;
        while (temp != null) {
            temp = temp.next;
            len++;
        }
        return len;
    }

    @Test
    public void test01() {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);

        ListNode res = getKthFromEnd1(head, 3);
        if (res != null) {
            System.out.println(getLength(head));
            System.out.println(res.val);
        } else {
            System.out.println("空");
        }
    }

    /**
     * 快慢指针法
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode getKthFromEnd1(ListNode head, int k) {
        ListNode first = head;
        while (first != null && k > 0) {
            first = first.next;
            k--;
        }

        ListNode second = head;
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        return second;
    }
}
